/* 

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

 

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：

输入：s = "a"
输出：[["a"]]
 

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 题解：https://leetcode-cn.com/problems/palindrome-partitioning/solution/shou-hua-tu-jie-san-chong-jie-fa-hui-su-q5zjt/

var partition = function (s) {
    const res = [];
    const memo = new Array(s.length);
    for (let i = 0; i < memo.length; i++) {
        memo[i] = new Array(s.length);
    }

    function dfs(temp, start) {
        if (start == s.length) {
            res.push(temp.slice());
            return;
        }
        for (let i = start; i < s.length; i++) {
            if (memo[start][i] === false) {
                continue
            }
            if (memo[start][i] || isPali(s, start, i, memo)) {
                temp.push(s.substring(start, i + 1));
                dfs(temp, i + 1);
                temp.pop();
            }
        }
    }
    dfs([], 0);
    return res;
};

function isPali(s, l, r, memo) {
    while (l < r) {
        if (s[l] != s[r]) {
            memo[l][r] = false;
            return false;
        }
        l++;
        r--;
    }
    memo[l][r] = true;
    return true;
}